package com.apkcore.bl;

public class _42接雨水 {
    public static void main(String[] args) {
//        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int[] height = {4, 2, 0, 3, 2, 5};
        System.out.println(new _42接雨水().trap0(height));
        System.out.println(new _42接雨水().trap1(height));
        System.out.println(new _42接雨水().trap(height));
    }

    /**
     * 双指针夹逼，
     * 柱子能接多少水，永远是由最小的那根柱子来决定的
     */
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        // 第一根和最后一根柱子肯定是不能放水的
        int left = 0;
        int right = height.length - 1;
        int water = 0;
        int leftMax = 0;
        int rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] >= height[right]) {
                water += rightMax - height[right];
                right--;
            } else {
                water += leftMax - height[left];
                left++;
            }
        }
        return water;
    }

    /**
     * 在上一个上面进行优化，取左边的最大值和最终求雨水这个for循环重复了，可以省去
     */
    public int trap1(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        // 第一根和最后一根柱子肯定是不能放水的
        int lastIdx = height.length - 2;
        int[] rightMaxes = new int[height.length];
        for (int i = lastIdx; i >= 1; i--) {
            rightMaxes[i] = Math.max(rightMaxes[i + 1], height[i + 1]);
        }

        int water = 0;
        int leftMax = 0;
        for (int i = 1; i <= lastIdx; i++) {
            leftMax = Math.max(leftMax, height[i - 1]);
            int min = Math.min(leftMax, rightMaxes[i]);
            // 左右都没有自己高，说明不能放水
            if (min <= height[i]) {
                continue;
            }
            water += min - height[i];
        }
        return water;
    }

    /**
     * 由左右两根最高的柱子决定了此柱子能放多少水
     */
    public int trap0(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        // 第一根和最后一根柱子肯定是不能放水的
        int lastIdx = height.length - 2;
        int[] leftMaxes = new int[height.length];
        int[] rightMaxes = new int[height.length];
        for (int i = 1; i <= lastIdx; i++) {
            leftMaxes[i] = Math.max(leftMaxes[i - 1], height[i - 1]);
        }
        for (int i = lastIdx; i >= 1; i--) {
            rightMaxes[i] = Math.max(rightMaxes[i + 1], height[i + 1]);
        }

        int water = 0;
        for (int i = 1; i <= lastIdx; i++) {
            int min = Math.min(leftMaxes[i], rightMaxes[i]);
            // 左右都没有自己高，说明不能放水
            if (min <= height[i]) {
                continue;
            }
            water += min - height[i];
        }
        return water;
    }
}